In digital image processing applications it can be desirable to extract a one-dimensional (1D) signal along a line in a two-dimensional (2D) digital image. Such applications can include, for example, inspection, measurement, and guidance for electronics, semiconductor, and general manufacturing, and barcode and other symbology reading.
The term projection is sometimes used to refer to the act of extracting a one-dimensional signal along a line, herein called a projection line, in a two-dimensional image. The term is sometimes also applied to the 1D signal itself, and sometimes has other meanings in the field of digital image processing.
In some methods or systems the projection line is restricted to lie along rows, columns, or diagonals of a digital image. In such cases a 1D signal can be extracted from pixel values that lie exactly on the projection line. The 1D signal can have samples that are one pixel apart for rows and columns, and √{square root over (2)} pixels apart for diagonals (assuming square pixels).
In other methods or systems where the projection line lies along rows, columns, or diagonals of a digital image, a 1D signal is extracted by summing or averaging pixel values perpendicular to the projection line. For example, if a projection lies along row 20 of a digital image, each sample of a 1D signal along that line can be the sum or average of pixel values along a portion of a column that includes rows 18, 19, 20, 21, and 22.
When a projection line does not lie along a row, column, or diagonal, pixels that lie exactly on the line, or in a direction perpendicular to the line, are in general sparsely located or nearly nonexistent. In some methods or systems where the projection line is not restricted to lie along rows, columns, or diagonals, therefore, a 1D signal is extracted from a set of pixels that approximately follows the projection line. One example of such a method is the so-called Bresenham line following method, which typically makes one-pixel steps along rows, columns, or diagonals in such a manner that the pixels visited lie approximately along the projection line.
In another method, herein referred to as linear convolution, a 1D signal is extracted by convolving the digital image with a 2D filter kernel at positions chosen by a Bresenham line following method. The filter kernel is designed to provide summing or averaging roughly perpendicular to the projection line. The filter kernel can have uniform weights, or the weights can become smaller for pixels farther from the projection line.
In another method, herein called skewed projection, pixels in a parallelogram pattern are used to extract a 1D signal. The parallelogram has two sides that lie along rows of the image, and the other two sides are at some skew angle, generally not along columns. The parallelogram is thus comprised of a certain number of consecutive pixels from each of a certain number of consecutive rows, with the starting columns for the pixels of the rows offset to approximately follow the skew angle. The 1D signal is formed by summing or averaging in the skew direction.
In another method, herein referred to as nearest neighbor projection, a grid of points are chosen that lie at some spacing along a projection line, typically one pixel, and at some spacing perpendicular to the projection line, typically also one pixel. The image coordinates of those points are rounded to the nearest integer so that they fall on pixel coordinates, and the pixels so specified are used to extract the 1D signal by summing or averaging approximately (in the nearest neighbor sense) perpendicular to the projection line.
In other methods, herein called bi-linear interpolation and bi-cubic interpolation, a grid of points is chosen in a manner similar to that used for nearest neighbor projection. Instead of rounding a point's coordinates to integers, however, the coordinates are used to compute an interpolated pixel value. These interpolated values are used to extract the 1D signal by summing or averaging perpendicular to the projection line. Formulas for bi-linear and bi-cubic interpolation are well known in the art.
Nearest neighbor projection and the interpolation methods achieve equivalent results as rotating the digital image so that the projection line lies along a row or column of the (rotated) image, and then summing or averaging perpendicular to the projection line. Here “equivalent” refers to the 1D signal obtained, but not necessarily the time needed to obtain it. Rotating a digital image is a type of image processing operation commonly called digital re-sampling.
In another method, equally-spaced lines are constructed perpendicular to a projection line. A 1D signal is extracted by a weighted summation of pixels along the perpendicular lines, where the weights are proportional to the length of the intersection of a line and a pixel.